package leetcode.editor.cn.dsa19_trie;

/**
 * 字典树，trie，前缀树
 */
public class TrieNode {
    private final int SIZE = 26; // 假设字典的元素都是小写字母
    TrieNode[] child; // 存储子结点
    boolean isWord; // 标记当前元素是否是单词的结尾
    public TrieNode() {
        isWord = false; // 初始化为false
        child = new TrieNode[SIZE]; // 子结点初始化为空
    }
    // 字典树的前序遍历
    public void preOrder(TrieNode root) {
        for (int i = 0; i < SIZE; i++) { // 访问根结点
            if (root.child[i] != null) {
                System.out.println(i + 'a');
                if (root.child[i].isWord) {
                    System.out.print("(end)");
                }
                System.out.print("\n");
                preOrder(root.child[i]); // 依次访问子树
            }
        }
    }
    // 字典树单词的插入
    public void insert(TrieNode root, String word) {
        char[] wordChar = word.toCharArray();
        TrieNode presentNode = root;
        for (int i = 0; i < wordChar.length; i++) { // 逐个遍历
            int wordPos = wordChar[i] - 'a'; // 计算位置
            if (presentNode.child[wordPos] == null) {
                // 不存在，则创建新结点
                presentNode.child[wordPos] = new TrieNode();
            }
            // 存在，则当前字符已经存在，移动指针
            presentNode = presentNode.child[wordPos];
        }
        presentNode.isWord = true; // 标记单词末尾
    }
    // 字典树的单词的搜索
    public boolean search(TrieNode root, String word) {
        char[] wordChar = word.toCharArray();
        TrieNode presentNode = root;
        for (int i = 0; i < wordChar.length; i++) { // 逐个遍历待搜索字符
            int wordPos = wordChar[i] - 'a'; // 计算位置
            if (presentNode.child[wordPos] == null) {
                return false; // 如果当前字符在Trie中不存在，搜索失败
            }
            // 继续向下搜索
            presentNode = presentNode.child[wordPos];
        }
        return presentNode.isWord; // 返回当前结点的标记
    }
}
